package com.stephen.data.sort;

/**
 * @author: stephen
 * @create: 2020-01-31 21:56
 * @description: 基数排序
 * 空间换时间,800w,不到1秒,比快排还快
 * 但是需要很多空间,可以会出现OutOfMemoryError
 * 8000w数据就会出现堆内存溢出
 * java.lang.OutOfMemoryError: Java heap space
 */
public class RadixSort {

    /**
     * 基数排序是稳定的(当序列中,有多个相同元素时,这些元素在排序之后的相对序列不会变)
     * 有负数时,不可用基数排序
     * @param args
     */
    public static void main(String[] args) {
        // int[] arr = {53,3,542,748,14,89};
        // sort(arr);

        // 测试排序时间
        int[] arrTest = new int[8000000];
        for (int i = 0; i < 8000000; i++) {
            arrTest[i] = (int)(Math.random() * 8000000);
        }
        int[] temp = new int[arrTest.length];
        long start = System.currentTimeMillis();
        sort(arrTest); // 9743 ms
        long end = System.currentTimeMillis();
        System.out.printf("排序时长: [%d]毫秒",end - start);
    }

    public static void sort(int[] arr) {
        // 定义一个二维数组,代表10个桶
        int[][] bucket = new int[10][arr.length];
        // 记录每个桶中,实际存放了多少个元素
        int[] bucketEleCount = new int[10];

        // 取出数组中的最大值
        int max = arr[0];
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        // 拿到最大值的位数
        int maxLength = (max + "" ).length();

        // 总共需要最大值的位数轮
        for (int i = 0,n = 1; i < maxLength; i++,n *= 10) {
            // 每一轮,针对每个元素的对应位进行排序,第1轮个位,第2轮十位,第3轮百位...
            for (int j = 0; j < arr.length; j++) {
                // 取出每个元素对应位的值
                int digitOfElement = arr[j] / n % 10;
                // 把该值放入对应的桶中
                // TODO 这个地方不太懂???
                bucket[digitOfElement][bucketEleCount[digitOfElement]] = arr[j];
                bucketEleCount[digitOfElement]++;
            }
            // 按照这个桶的顺序,即一维数组的下标依次取出数据,放入原来数组
            int index = 0;
            for (int k= 0; k < bucketEleCount.length; k++) {
                // 如果桶中有数据,才放入到原来数组
                if (bucketEleCount[k] != 0) {
                    // 循环该桶,即第k个一维数组,放入
                    for(int l = 0; l < bucketEleCount[k]; l++) {
                        // 取出元素放入到arr
                        arr[index++] = bucket[k][l];
                    }
                }
                // 每轮结束,要bucketEleCount[k] = 0
                bucketEleCount[k] = 0;
            }
            // System.out.printf("第[%d]轮的排序结果 arr=" + Arrays.toString(arr) + "\n",i + 1);
        }

    }
}
